package com.hooper.solution.day14;

class Solution {
    /**
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
     * 示例 1：
     * <p>
     * 输入：nums = [5,7,7,8,8,10], target = 8
     * 输出：[3,4]
     * 示例 2：
     * <p>
     * 输入：nums = [5,7,7,8,8,10], target = 6
     * 输出：[-1,-1]
     * 示例 3：
     * <p>
     * 输入：nums = [], target = 0
     * 输出：[-1,-1]
     */
    public int[] searchRange(int[] nums, int target) {
        int left = leftMost(nums, target);
        return left == -1 ? new int[]{-1, -1}
                : new int[]{left, rightMost(nums, target)};
    }

    /**
     * 二分查找 - LeftMost
     * 若有相同元素，返回最左侧元素的下标
     *
     * @param arr    目标数组
     * @param target 查找的值
     * @return 目标值的下标, 若有相同元素，返回该元素最左侧的下标  查询不到返回-1
     */
    public static int leftMost(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int candidate = -1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (target < arr[mid]) {
                right = mid - 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                candidate = mid;
                right = mid - 1;
            }
        }
        return candidate;
    }

    /**
     * 二分查找 - RightMost
     * 若有相同元素，返回最右侧元素的下标
     *
     * @param arr    目标数组
     * @param target 查找的值
     * @return 目标值的下标, 若有相同元素，返回该元素最右侧的下标 查询不到返回-1
     */
    public static int rightMost(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int candidate = -1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (target < arr[mid]) {
                right = mid - 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                candidate = mid;
                left = mid + 1;
            }
        }
        return candidate;
    }

    public static void charCount(String str) {
        str = str.toLowerCase();
        int[] ans = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            ++ans[c - 'a'];
        }
        for (int i = 0; i < str.length(); i++) {
            int index = str.charAt(i) - 'a';
            int count = ans[index];
            if (count != 0){
                System.out.println(str.charAt(i) + "出现了" + count + "次");
                ans[index] = 0;
            }
        }
    }
}